Various methods for curve fitting and curve design have been developed in the fields of Computer Graphics and Geometric Modeling. The most actively used methods employ polynomial and piecewise-polynomial curves, such as Bezier curves and parametric splines, discussed by Gerald Farin in “Curves and Surfaces for CAGD” (Practical Guide, 5th ed., 2002), by David Salomon in “Computer Graphics & Geometric Modeling” (1999), and by many other authors.
There are both automated and interactive procedures for fitting a spline to interpolate or approximate a sequence of data points. In a process of fitting, a number of parameters can be adjusted to produce a better spline curve, for example, in terms of ‘fairness’ or aesthetical pleasing. In particular, the tangent vectors at the endpoints can be modified, and the sequence of data points can be reparameterized. In case of interactive curve design, the data points themselves, along with the control points, can be moved by a user to adjust the spline curve. As noticed by Gerald Farin, many designers do not favor interactive manipulation of a control polygon and prefer to generate curves using interpolation of data points (see Gerald Farin, “Curves and Surfaces for CAGD,” Section 2.4).
In case of noisy data points, the curve fitting procedures are routinely accompanied by digital filtering. Most often filtering is not involved directly into the curve generation procedure and is used as the data preprocessing step. An example can be given by a method described in the U.S. Pat. No. 6,304,677 issued to Michael Schuste and entitled Smoothing and Fitting Point Sequences. According to this patent, an initial sequence of points is divided into one or more contiguous segments, each segment is smoothed by digital filtering, and then one or more mathematical curves (in particular, splines) are fitted to each segment to form the representation of the desired curve.
It is also possible for filtering to serve both the data smoothing and curve generation steps. A technique of this type is described in the U.S. application Ser. No. 11/013,869 invented by B. E. Gorbatov et al., entitled System and Method for Handling Electronic Ink, the teachings of which are hereby incorporated by this reference. According to this technique, a fitting curve with desired sampling density is generated by filtering an upsampled polygonal representation of noisy data points. This operation is repeatedly used in the trial and error procedure of discarding excessive data points.
There are also curve generation methods, such as subdivision schemes for B-splines, comprising digital filtering as an essential part of the curve formation procedure. Several examples of using filter technology to construct subdivision schemes are discussed in Igor Guskov et al., “Multiresolution Signal Processing for Meshes” 325-334 (Proceedings of SIGGRAPH 99, Annual Conference Series, 1999); Leif Kobbelt & Robert Schroder, “A Multiresolution Framework for Variational Subdivision” 209-237 (ACM Transactions on Graphics 17(4), 1998); and Leif Kobbelt, “Discrete Fairing and Variational Subdivision for Freeform Surface Design” 142-150 (The Visual Computer 16(3-4), 2000). In one example, a subdivision procedure for cubic B-spline can start with the control polygon upsampled by inserting a zero-valued sample between each pair of original vertices and proceed with filtering. The result of filtering should be equivalent to four rounds of midpoint averaging (see Joe Warren & Henrik Weimer, “Subdivision Methods for Geometric Design. A Constructive Approach”, 2002).
It should be noted that, in practice, the fitting quality of polynomial splines is not always readily acceptable for a given application. Often, laborious interactive improvement is required before the fitting quality of polynomial splines becomes acceptable.